package com.learn.string;

/**
 * 求解最长回文子串的长度,Manacher算法用于求解最长回文字串问题
 */
public class Manacher {

    public int getSubLength(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        sb.append("#");
        for (char ch : chars) {
            sb.append(ch);
            sb.append("#");
        }
        //将原始字符串左右两边都添加#符号，用来求解最长回文
        String string = sb.toString();

        int res = 1;
        for (int i = 1; i < string.length(); i++) {

            int R = i + 1;
            int L = i - 1;
            while (R < string.length() && L > -1) {
                if (string.charAt(L) == string.charAt(R)) {
                    L--;
                    R++;
                } else {
                    L++;
                    R--;
                    break;
                }
            }
            if (L < 0 || R >= string.length()) {
                res = Math.max(res, (R - L + 1 - 2) / 2);
            } else {
                res = Math.max(res, (R - L + 1) / 2);
            }


        }

        return res;
    }


    public int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        sb.append("#");
        for (char ch : chars) {
            sb.append(ch);
            sb.append("#");
        }

        char[] changeArr = sb.toString().toCharArray();
        //回文最右半径,第一次扩失败的位置
        int R = -1;
        //回文中心点
        int C = -1;
        //记录每个位置的回文半径
        int[] pArr = new int[changeArr.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < changeArr.length; i++) {

            //R为第一个违规的位置,i>=R时，表示i在R外
            //R>i代表i在R内
            //当前pArr[i]代表不需要验证的区域
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;

            while (i + pArr[i] < changeArr.length && i - pArr[i] > -1) {
                if (changeArr[i + pArr[i]] == changeArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }

            //如果当前位置+回文半径超过R,R需要更新，i作为新的中心点
            if (i + pArr[i] > R) {
                R = pArr[i] + i;
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }

        return max - 1;
    }

    public static void main(String[] args) {
        String s = "123321";
        Manacher manacher = new Manacher();
        System.out.println(manacher.manacher(s));
        System.out.println(manacher.getSubLength(s));
    }
}
